package dp01;

import java.util.Arrays;

/**
 * 题目：打家劫舍2
 * 题目链接：https://leetcode.cn/problems/house-robber-ii/solutions/722767/da-jia-jie-she-ii-by-leetcode-solution-bwja/
 * 思路：把这个环分成串，但是分两种情况，第一种情况不偷第一家，那么就是打家劫舍1题目从1->n-1位置
 * 第二种情况，偷第一家，那么最后一家，和第二家不能被偷，所以就是打家劫舍1从2->n-2加上nums[0];
 */
public class Solution8 {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + massage(nums,2,n-2),massage(nums,1,n-1));
    }

    public static int massage(int[] nums , int left , int right) {
        int n = nums.length;
        if(n == 0) return 0;   //防止没有预约
        int[] f = new int[n];  //表示该点被选上
        int[] g = new int[n];   //表示该点没被选上
        f[left] = nums[left];
        for (int i = left+1; i <= right; i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }
}
